Previous | Index | Next |

Associative containers

Associative containers provide an ability for fast retrieval of data based on keys. There are two major categories of associated containers: sorted associated containers and hashed associated containers, the latter are also called hash tables. These categories share many requirements, which we call the base requirements for associated containers.

The library provides four basic kinds of sorted associative containers: Set api, MultiSet api, Map api and MultiMap api and four basic kinds of hash tables: HashSet api, HashMultiSet api, HashMap api and HashMultiMap api.

All of the sorted associated containers are parameterized with an ordering relation compare that induces a total ordering on elements of the containers. In addition, Map and MultiMap associate an arbitrary object with the key. The object of type Predicate2 is called the comparison object of a container.

All of the hash tables are parammeterized on a hash function HashFunction api that maps element of the keyinto integers, and a Predicate2 function that induces an equivalens relation on the elements of the key. In addition, HashMap and HashMultiMap associate an arbitrary object with the key.

With sorted associated containers, when we talk about equality of keys we mean the equivalence relation imposed by the comparison object. That is, two keys k1 and k2 are considered to be equal if for the comparison object comp, comp.compare(k1, k2) == false && comp.compare(k2, k1) == false.

With hash tables, when we talk about equality of keys we mean equivalens relation imposed by the key-equivalens object and not the == operation. That is, two keys k1 and k2 are considered to be equal if for the key-equivalens object comp, comp.compare(k1, k2) == true.

An associative container (either sorted or hashed) supports unique keys if it may contain at most one element for each key. Otherwise, it supports equal keys. Set, Map, HashSet and HashMap support unique keys. MultiSet, MultiMap, HashMultiSet and HashMultiMap support equal keys.

For Set, MultiSet, HashSet and HashMultiSet the value object is the same as the key object. For Map, MultiMap, HashMap and HashMultiMap it is equal to Pair(Object key, Object value).

Iterators of a sorted associative container is of the bidirectional iterator category, while that of hash tables is of the forward iterator category. insert does not affect the validity of iterators and references to the container, and erase invalidates only the iterators and references to the erased elements.

In the following table, X is an associative container class, a is an instance of X, a_uniq is an instance of X when X supports unique keys, and a_eq is an instance of X when X supports multiple keys, i and j satisfy input iterator requirements, [i,j) is a valid range, p is a valid iterator to a, q is a dereferenceable iterator to a, [q1,q2) is a valid range in a, t is a value object and k is a key object.

The associative requirements are defined in the AssociativeContainer api interface.

Base requirements for associative container (in addition to container).
expression return type assertion/note
pre/post-condition
complexity
a_uniq.insert(t) pair(Iterator,Boolean) inserts t if and only if there is no element in the container with key equal to the key of t. The Boolean component of the returned pair indicates whether the insertion takes place and the Iterator component of the pair points to the element with key equal to the key of t. expected logarithmic
a_eq.insert(t) Iterator inserts t and returns the iterator pointing to the newly inserted element. expected logarithmic
a.insert(i, j) void inserts the elements from the range [i,j) into the container. Expected Nlog(size()+N) (N is the distance from i to j) in general; expected linear if [i,j) is sorted according to c
a.erase(k) int erases all the elements in the container with key equal to k.
returns the number of erased elements.
expected log(size()) + count(k)
a.erase(q) void erases the element pointed to by q. expected constant
a.erase(q1, q2) void erases all the elements in the range [q1,q2). log(size())+ N where N is the distance from q1 to q2.
a.find(k) Iterator returns an iterator pointing to an element with the key equal to k, or a.end() if such an element is not found. expected logarithmic
a.count(k) int returns the number of elements with key equal to k. expected log(size()) + count(k)
a.equal_range(k) pair(Iterator,Iterator) returns iterators i and j such that all elements with keys equal to k are in the range [i,j). This range is empty if no elements have key k. expected logarithmic

The table entrie in the complexity column are in some cases qualified by the word expected, meaning that the expected (or average) time in required to satisfy the indicated bound, rather than the worst-case time. For example expected logarithmic means that the expected time must be O(log size()), which is as looser requirement than requiring the worst-case time to be logarithmic. Note that an expected time requirement is also met by an implementation for which the amortized meets the bound; i.e., the stated expected time requirements allow implementations with either expected or amortized time bounds.


Previous | Index | Next |